package com.jsy.common.leetcode;

import com.sun.jmx.remote.internal.ArrayQueue;
import io.swagger.models.auth.In;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;

class Solution3 {
    public Node4 construct(int[][] grid) {
        return construct(grid, 0, grid.length-1, 0, grid[0].length-1);
    }

    private Node4 construct(int[][] grid, int rowStart, int rowEnd, int columnStart, int columnEnd) {
        if (rowStart == rowEnd && columnStart == columnEnd){
            return new Node4(grid[rowStart][columnStart] == 1, true);
        }
        int times = (rowEnd - rowStart) / 2;
        Node4 topLeft = construct(grid, rowStart, rowStart + times, columnStart, columnStart+times);
        Node4 bottomLeft  = construct(grid, rowStart + times + 1, rowEnd, columnStart, columnStart+times);
        Node4 topRight = construct(grid, rowStart, rowStart + times, columnStart+times+1, columnEnd);
        Node4 bottomRight = construct(grid, rowStart+times+1, rowEnd, columnStart+times+1, columnEnd);
        if (topLeft.val == topRight.val && topLeft.val == bottomLeft.val && topLeft.val == bottomRight.val && topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf) {
            return new Node4(topLeft.val, true,null, null, null, null);
        }
        return new Node4(topLeft.val, false, topLeft, topRight, bottomLeft, bottomRight);
    }

    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            sum+=nums[i];
            max = Math.max(sum, max);
            if (sum<=0){
                sum=0;
            }
        }
        return max;
    }


    public int maxSubarraySumCircular(int[] nums) {
        int length = nums.length;
        int max = Integer.MIN_VALUE;
        int sum = 0;
        int leftSum = 0;
        int[] leftMax = new int[length];
        for (int i = 0; i < length; i++) {
            sum += nums[i];
            max = Math.max(sum, max);
            leftSum += nums[i];
            if (i == 0){
                leftMax[i] = nums[i];
            }else {
                leftMax[i] = Math.max(leftMax[i - 1], leftSum);
            }
            if (sum <= 0) {
                sum = 0;
            }
        }
        int rightSum = 0;
        for (int j = 0; j < length-1; j++) {
            rightSum +=nums[length-1-j];
            max = Math.max(max, rightSum + leftMax[length - 1 - j - 1]);
        }
        return max;
    }

    public int maxSubarraySumCircular2(int[] nums) {
        int length = nums.length;
        int preMax = nums[0];
        int maxRes = nums[0];
        int preMin = nums[0];
        int minRes = nums[0];
        int sum = 0;
        for (int i = 0; i < length; i++) {
            preMax = Math.max(preMax + nums[i], nums[i]);
            maxRes = Math.max(maxRes, preMax);
            preMin = Math.min(preMin + nums[i], nums[i]);
            minRes = Math.min(minRes, preMin);
            sum += nums[i];
        }
        if (maxRes < 0){
            return maxRes;
        }else {
            return Math.max(maxRes, sum - minRes);
        }
    }

    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (target<=nums[i]){
                return i;
            }
        }
        return nums.length;
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert2(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
//       return searchInsert(nums, target, 0, nums.length-1);
    }

    private int searchInsert(int[] nums, int target, int left, int right) {
        if (left>right){
            return left;
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target){
            return mid;
        }
        if (nums[mid] > target){
            return searchInsert(nums, target, left, mid-1);
        }else {
            return searchInsert(nums, target, mid+1, right);
        }
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int leftRow = 0, leftColum = 0, rightRow = m - 1, rightColum = n - 1;
        while (leftRow <= rightRow && leftColum <= rightColum) {
            int midRow = (leftRow + rightRow) / 2;
            int midColum = (leftColum + rightColum) / 2;
            if (target == matrix[midRow][midColum]) {
               return true;
            }else {
                if (target < matrix[midRow][midColum]) {
                    if (target < matrix[midRow][0]) {
                        rightRow = midRow - 1;
                    } else {
                        rightColum = midColum - 1;
                    }
                }else {
                    if (target > matrix[midRow][n - 1]) {
                        leftRow = midRow + 1;
                    } else {
                        leftColum = midColum + 1;
                    }
                }
            }
        }
        return false;
    }

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[left] <= nums[mid]) {
               if (target >= nums[left] && target < nums[mid]){
                   right = mid - 1;
               }else {
                   left = mid + 1;
               }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        int length = nums.length;
        int left = 0;
        int right = length - 1;
        int[] res = {-1, -1};
        return searchRange(nums, target, left, right, res);
    }

    private int[] searchRange(int[] nums, int target, int left, int right, int[] res) {
        if (left > right){
            return new int[]{-1, -1};
        }
        int mid = (left + right) / 2;
        if (nums[mid] == target){
            if (res[0] == -1){
                res[0] = mid;
            }
            res[0] = Math.min(res[0], mid);
            res[1] = Math.max(res[1], mid);
            searchRange(nums, target, left, mid - 1,res);
            searchRange(nums, target, mid + 1, right,  res);
        }else if (nums[mid] > target){
            searchRange(nums, target, left, mid - 1, res);
        }else {
            searchRange(nums, target, mid + 1, right,  res);
        }
        return res;
    }

    public int findMin(int[] nums) {
//        return findMin(nums, 0, nums.length - 1);
        return findMin2(nums, 0, nums.length - 1);
    }

    private int findMin(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        if (left>right){
            return nums[mid];
        }
        if (mid-1 >= 0 && mid+1 < nums.length && nums[mid] <= nums[mid+1] && nums[mid] <= nums[mid-1]){
           return nums[mid];
        }
        int leftMin = findMin(nums, left, mid - 1);
        int rightMin = findMin(nums, mid + 1, right);
        return Math.min(leftMin, rightMin);
    }

    private int findMin2(int[] nums, int left, int right) {
        int mid = (left + right) / 2;
        if (left>right){
            return nums[left];
        }
        if (nums[mid] < nums[right]){
         return findMin2(nums, left, mid);
        }else {
         return findMin2(nums, mid + 1, right);
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] merge = new int[(m+n)/2+1];
        int index = 0;
        int nums1Index = 0;
        int nums2Index = 0;
        while (index<merge.length && nums1Index<m && nums2Index<n){
            if (nums1[nums1Index] < nums2[nums2Index]){
                merge[index++] = nums1[nums1Index++];
            }else {
                merge[index++] = nums2[nums2Index++];
            }
        }
        while (index<merge.length && nums1Index<m){
            merge[index++] = nums1[nums1Index++];
        }
        while (index<merge.length && nums2Index<n){
            merge[index++] = nums2[nums2Index++];
        }
        if ((m+n)%2 == 0){
            return (merge[(m+n)/2] + merge[(m+n)/2 - 1])/2.0;
        }else {
            return merge[(m+n)/2];
        }
    }

    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public int findKthLargest2(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int length = profits.length;
        //1. 将启动资金和利润封装到数组中
        int[][] arrs = new int[length][2];
        for (int i = 0; i < length; i++) {
            arrs[i][0] = capital[i];
            arrs[i][1] = profits[i];
        }
        // 2.按照启动资金将数组由小到大排列
        Arrays.sort(arrs, (o1, o2) -> o1[0] - o2[0]);
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        int curr = 0 ;
        // 3. 遍历数组，将启动资金小于等于w的利润放入优先队列中，优先队列中保存利润最大的值
        for (int i = 0; i < k; i++) {
            while (curr<length && w >= arrs[curr][0]){
                queue.offer(arrs[curr][1]);
                curr++;
            }
            if (!queue.isEmpty()){
                w += queue.poll();
            }else {
                break;
            }
        }
        return w;
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> res = new ArrayList<>();
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if(queue.size()>2*k){
                    queue.offer(new int[]{nums1[i], nums2[j]});
                }
            }
        }
        while (k>0){
            int[] poll = queue.poll();
            res.add(Arrays.asList(poll[0], poll[1]));
            k--;
        }
        return res;
    }

    public List<List<Integer>> kSmallestPairs2(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>(k); // 预分配空间
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < Math.min(nums1.length, k); i++) { // 至多 k 个
            pq.add(new int[]{nums1[i] + nums2[0], i, 0});
        }
        while (ans.size() < k) {
            int[] p = pq.poll();
            int i = p[1];
            int j = p[2];
            ans.add(Arrays.asList(nums1[i], nums2[j]));
            if (j + 1 < nums2.length) {
                pq.add(new int[]{nums1[i] + nums2[j + 1], i, j + 1});
            }
        }
        return ans;
    }


    public String addBinary(String a, String b) {
        StringBuilder builder = new StringBuilder();
        int aLen = a.length();
        int bLen = b.length();
        int i = aLen - 1;
        int j = bLen - 1;
        int carry = 0;
        while (i >= 0 || j>=0){
            char aChar = '0';
            if (i>=0){
                aChar = a.charAt(i);
                i--;
            }
            char bChar = '0';;
            if (j>=0){
                bChar = b.charAt(j);
                j--;
            }
            int add = add(aChar, bChar)+carry;
            int ans = add%2;
            carry = add/2;
            builder.append(ans);
        }
        if (carry==1){
            builder.append('1');
        }
        return builder.reverse().toString();
    }

    public int add(char a, char b){
        if (a=='0' && b=='0'){
            return 0;
        }else if (a=='0' && b=='1'){
            return 1;
        }else if (a=='1' && b=='0'){
            return 1;
        }else {
            return 2;
        }
    }

    /**
     * 翻转二进制
     * @param n
     * @return
     */
    public int reverseBits(int n) {
        int rev = 0;
        for (int i = 0; i < 32 && n != 0; ++i) {
            rev |= (n & 1) << (31 - i);
            n >>>= 1;
        }
        return rev;
    }

    public int hammingWeight(int n) {
        int count = 0;
        int cur = n;
        while (cur !=0){
            if ((cur & 1) == 1){
                count++;
            }
            cur = cur>>1;
        }
        return count;
    }

    public int singleNumber(int[] nums) {
        int single = 0;
        for (int i = 0; i < nums.length; i++) {
            single = single^nums[i];
        }
        return single;
    }

    public int singleNumber2(int[] nums) {
        HashMap<Integer, Integer> numsMap = new HashMap<>();
        int single = 0;
        for (int i = 0; i < nums.length; i++) {
            if (numsMap.getOrDefault(nums[i],0) > 1){
                continue;
            }
            numsMap.put(nums[i], numsMap.getOrDefault(nums[i], 0)+1);
            single = single ^ nums[i];
        }
        return single;
    }

    /**
     * 数字按位与
     * @param left
     * @param right
     * @return
     */
    public int rangeBitwiseAnd(int left, int right) {
        int res = 0;
        while(left<right){
            right=right&(right-1);
        }
        return right;
    }
    public boolean isPalindrome(int x) {
        if (x<0 || x%10==0){
            return false;
        }
        int res = 0;
        while(x>res){
            res = res * 10 + x%10;
            x = x/10;
       }
       return x == res || x == res / 10;
    }

    public int[] plusOne(int[] digits) {
        int carry = 1;
        for (int i = 0; i < digits.length; i++) {
            if (carry==0){
                return digits;
            }
            if (digits[digits.length-1-i]+carry>9){
                digits[digits.length-1-i] = 0;
            }else {
                digits[digits.length-1-i] = digits[digits.length-1-i]+carry;
               carry = 0;
            }
        }
        if (carry==1){
            int[] res = new int[digits.length+1];
            res[0] = 1;
            for (int i = 0; i < digits.length; i++) {
                res[i+1] = digits[i];
            }
            return res;
        }else {
            return digits;
        }
    }

    /**
     * 阶乘后的0
     * @param n
     * @return
     */
    public int trailingZeroes(int n) {
        int ans = 0;
//        for (int i = 5; i < n; i=i+5) {
//            for (int j = i;j%5==0; j=j/5){
//                ans++;
//            }
//        }
        while (n!=0){
            n = n/5;
            ans += n;
        }
       return ans;
    }

    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int count = 0;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            for (int j = i+1; j < length; j++) {
                for (int k = j+1; k < length; k++) {
                    if (Math.abs(arr[i]-arr[j])<=a && Math.abs(arr[j]-arr[k])<=b && Math.abs(arr[i]-arr[k])<=c){
                        System.out.println(count++);
                    }
                }
            }
        }
        return count;
    }

    public int mySqrt(int x) {
        if (x==0 || x==1){
            return x;
        }
        int low = 0;
        int high = x;
        int ans = -1;
        while (low<=high){
           int mid = low + (high-low)/2;
           if (mid*mid<=x){
               ans= mid;
               low = mid+1;
           }else {
               high = mid-1;
           }
        }
        return ans;
    }

    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul2(x, N) : 1.0 / quickMul2(x, -N);
//        return Math.pow(x,n);
    }

    private double quickMul2(double x, long N) {
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul2(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }

    private double quickMul(double x, long N) {
        double ans = 1.0;
        // 贡献的初始值为 x
        double x_contribute = x;
        // 在对 N 进行二进制拆分的同时计算答案
        while (N > 0) {
            if (N % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                ans *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            N /= 2;
        }
        return ans;
    }

    public int maxPoints(int[][] points) {
        int ans = 1;
        for (int i = 0; i < points.length; i++) {
            int[] x = points[i];
            for (int j = i+1; j < points.length; j++) {
                int[] y = points[j];
                int cnt = 2;
                for (int k = j+1; k < points.length; k++) {
                    if ((y[1] - x[1]) * (points[k][0] - y[0])==(points[k][1] - y[1]) * (y[0] - x[0])){
                        cnt++;
                    }
                }
                ans = Math.max(ans, cnt);
            }
        }
        return ans;
    }

    /**
     * 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int p = 0 ; int q = 0; int r = 1;
        for (int i = 0; i < n; i++) {
             p = q;
             q = r;
             r = p + q;
        }
        return r;
    }

    /**
     * 抢红包
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
       int pre = 0; int cur = 0;
       for (int i = 0; i < nums.length; i++) {
           int temp = cur;
           cur = Math.max(cur, pre + nums[i]);
           pre = temp;
       }
       return cur;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
       return wordBreak(s, wordDict,0);
    }

    private boolean wordBreak(String s, List<String> wordDict, int index) {
        if (index == s.length()){
            return true;
        }
        for (int i = index; i < s.length(); i++) {
            if (wordDict.contains(s.substring(index, i+1))){
                if (wordBreak(s, wordDict, i+1)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean wordBreak2(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for(int j = 0; j < i; j++) {
                if (dp[j] && set.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    public int coinChange(int[] coins, int amount) {
       return coinChange(coins, amount, 0);
    }

    private int coinChange(int[] coins, int amount, int step) {
        if (amount == 0){
            return step;
        }
        if (amount < 0){
            return -1;
        }
        for (int coin : coins) {
            int res = coinChange(coins, amount - coin, step + 1);
            if (res != -1){
                return res;
            }
        }
        return step;
    }


    public int coinChange2(int[] coins, int amount) {
        int [] dp = new int[amount+1];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = amount+1;
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i - coin] != amount+1){
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        if (dp[amount] == amount+1){
            return -1;
        }
        return dp[amount];
    }

//    public int lengthOfLIS(int[] nums) {
//        int res = 0;
//        for (int i = 0; i < nums.length; i++) {
//            int count = 1;
//            int pre = nums[i];
//            for (int j = i+1; j < nums.length; j++) {
//                if (pre < nums[j]){
//                    count++;
//                    pre = nums[j];
//                }
//            }
//            res = Math.max(res, count);
//        }
//        return res;
//
//    }

    public int[] buildArray(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }

    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int max = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size()+1];
        for (int i = triangle.size()-1; i >=0; i--) {
            List<Integer> list = triangle.get(i);
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + list.get(j);
            }
        }
        return dp[0];
    }

    public int minPathSum(int[][] grid) {
       if (grid == null || grid.length == 0 || grid[0].length == 0){
           return 0;
       }
       int rows = grid.length;
       int columns = grid[0].length;
       int [][] dp = new int[rows][columns];
       for (int i = 0; i < rows; i++) {
           for (int j = 0; j < columns; j++) {
               if (i == 0 && j == 0){
                   dp[i][j] = grid[i][j];
               }else if (i == 0){
                   dp[i][j] = dp[i][j-1] + grid[i][j];
               }else if (j == 0){
                   dp[i][j] = dp[i-1][j] + grid[i][j];
               }else {
                   dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
               }
           }
       }
       return dp[rows-1][columns-1];
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
      int [] dp = new int[obstacleGrid[0].length];
      dp[0] = 1;
      for (int i = 0; i < obstacleGrid.length; i++) {
          for (int j = 0; j < obstacleGrid[0].length; j++) {
              if (obstacleGrid[i][j] == 1){
                  dp[j] = 0;
                  continue;
              }
              if (j > 0 && obstacleGrid[i][j-1] == 0){
                  dp[j] += dp[j-1];
              }
          }
      }
      return dp[obstacleGrid[0].length-1];
    }
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2){
            return s;
        }
        String res = String.valueOf(s.charAt(0));
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            for (int j = i+1; j < chars.length; j++){
                if (chars[i] == chars[j]){
                    int left = i;
                    int right = j;
                    while (left < right){
                        if (chars[left] == chars[right]){
                            left++;
                            right--;
                        }else {
                            break;
                        }
                    }
                    if (left >= right){
                        if (res.length() == 0 || j - i + 1 > res.length()){
                            res = s.substring(i, j + 1);
                        }
                    }
                }
            }
        }
        return res;
    }

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        if (n + m != t) {
            return false;
        }
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i>0){
                    dp[i][j] = dp[i][j] ||  dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                }
                if (j>0){
                    dp[i][j] = dp[i][j] || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                }
            }
        }
        return dp[n][m];
    }

    public boolean isInterleave2(String s1, String s2, String s3) {
        int n = s1.length(), m = s2.length(), t = s3.length();
        if (n + m != t) {
            return false;
        }
        boolean[] dp = new boolean[m + 1];
        dp[0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i>0){
                    dp[j] = dp[j] && s1.charAt(i - 1) == s3.charAt(i + j - 1);
                }
                if (j>0){
                    dp[j] = dp[j] || dp[j-1] && s2.charAt(j - 1) == s3.charAt(i + j - 1);
                }
            }
        }
        return dp[m];
    }
    // 提供个更简单的思路
    // 如果遍历相同 直接取左下角的值
    // 如果不相同 左 下 左下取最小值 +1
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        if (n * m == 0) {
            return n + m;
        }
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j < m + 1; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
               int left = dp[i - 1][j] + 1;
               int down = dp[i][j - 1] + 1;
               int leftDown = dp[i - 1][j - 1];
               if (!word1.substring(i - 1, i).equals(word2.substring(j - 1, j))) {
                   leftDown += 1;
               }
               dp[i][j] = Math.min(Math.min(left, down), leftDown);
            }
        }
        return dp[n][m];
    }

    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }

    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);
            }
        }

        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }

    /**
     * 最大正方形
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }
        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }


    public static void main(String[] args) {
//        Node4 construct = new Solution3().construct(new int[][]{{0, 1}, {1, 0}});
//        Node4 construct = new Solution3().construct(new int[][]{{1,1,1,1,1,1,1,1}, {1,1,1,1,1,1,1,1},{1,1,1,1,1,1,0,0},{1,1,1,1,1,1,0,0},{1,1,1,1,1,1,1,1},{1,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1},{0,0,0,0,1,1,1,1}});
//        int maxSum = new Solution3().maxSubarraySumCircular(new int[]{5, -3, 5});
//        int maxSum = new Solution3().maxSubarraySumCircular(new int[]{-5,3,5});
//        int maxSum = new Solution3().maxSubarraySumCircular(new int[]{3,1,3,2,6});
//        int maxSum = new Solution3().search(new int[]{4,5,6,7,0,1,2}, 0);
//        int[] ints = new Solution3().searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8);
//        int[] ints = new Solution3().searchRange(new int[]{5,7,7,8,8,10}, 6);
//        int ints = new Solution3().findMin(new int[]{5,1,2,3,4});
//        int ints = new Solution3().findMin(new int[]{2,1});
//        int ints = new Solution3().findMaximizedCapital(2,0,new int[]{1,2,3},new int[]{0,1,1});
//        int ints = new Solution3().findMaximizedCapital(3,0,new int[]{1,2,3},new int[]{0,1,2});
//        MedianFinder medianFinder = new MedianFinder();
//        medianFinder.addNum(1);
//        medianFinder.addNum(2);
//        medianFinder.addNum(3);
//        double median = medianFinder.findMedian();
//        System.out.println(median);
//        String s = new Solution3().addBinary("1010", "1011");
//        String s = new Solution3().addBinary("11", "1");
//        int s = new Solution3().singleNumber2(new int[]{2,2,3,2});
//        boolean s = new Solution3().isPalindrome(121);
//        int[] s = new Solution3().plusOne(new int[]{1,2,3});
//        int s = new Solution3().countGoodTriplets(new int[]{3,0,1,1,9,7},7,2,3);
//        int s = new Solution3().mySqrt(8);
//        double s = new Solution3().myPow(2,-2);
//        double s = new Solution3().maxPoints(new int[][]{{1,1},{2,2},{3,3}});
//        double s = new Solution3().maxPoints(new int[][]{{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}});
//        int s = new Solution3().climbStairs(5);
//        int s = new Solution3().lengthOfLIS(new int[]{7, 7, 7, 7, 7, 7, 7});
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> integers = new ArrayList<>();
        integers.add(-1);
        list.add(integers);
        integers = new ArrayList<>();
        integers.add(2);
        integers.add(3);
        list.add(integers);
        integers = new ArrayList<>();
        integers.add(1);
        integers.add(-1);
        integers.add(-3);
        list.add(integers);
        int s = new Solution3().minimumTotal(list);
        System.out.println(s);
//        System.out.println(maxSum);
//        System.out.println(ints);
    }
}